package leetcode.editor.cn.dsa02_linkedlist;
//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 示例： 
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
// 
// Related Topics 链表 数学 
// 👍 5279 👎 0

public class AddTwoNumbers2 {

    //leetcode submit region begin(Prohibit modification and deletion)
    public class ListNode {
        int val; // 数据域
        ListNode next; // 指针域，指向下一个节点
        ListNode() {}
        ListNode(int val) { this.val = val; }
    }
    class Solution {
        /**
         * 暴力解法：
         * 遍历两个链表使用数学思维分别将他们转成整数
         * 对两个整数进行求和得到sum
         * 将sum按照数学思维再转成链表
         * 手动测试：
         * 若超过语言支持的数据类型范围，则报错
         * 解决办法： BigInteger
         *
         * @param l1
         * @param l2
         * @return
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            long l1Value = 0; // 链表l1代表的数字
            int digit = 0; // 位数
            while (l1 != null) {
                int pow = (int)Math.pow(10, digit); // 10的n次幂
                l1Value += l1.val * pow;
                l1 = l1.next; // //链表指向下⼀个节点
                digit++;
            }
            long l2Value = 0; // 链表l2代表的数字
            digit = 0;
            while (l2 != null) {
                int pow = (int) Math.pow(10, digit);
                l2Value += l2.val * pow;
                l2 = l2.next;
                digit++;
            }
            ListNode head = new ListNode();
            ListNode cur = head;
            // 两数相加
            long sum = l1Value + l2Value;
            if (sum == 0) {
                head = new ListNode(0);
                return head;
            }
            // 数字再转成链表
            while (sum > 0) {
                int val = (int)sum % 10; // 取当前最低位
                sum = sum / 10; // 移除最低位
                cur.next = new ListNode(val); // 创建新节点，插入链表尾部
                cur = cur.next; // 链表尾部指针移动
            }
            return head.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}